//给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 
//
// 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 
//
// 假设每一种面额的硬币有无限个。 
//
// 题目数据保证结果符合 32 位带符号整数。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：amount = 5, coins = [1, 2, 5]
//输出：4
//解释：有四种方式可以凑成总金额：
//5=5
//5=2+2+1
//5=2+1+1+1
//5=1+1+1+1+1
// 
//
// 示例 2： 
//
// 
//输入：amount = 3, coins = [2]
//输出：0
//解释：只用面额 2 的硬币不能凑成总金额 3 。
// 
//
// 示例 3： 
//
// 
//输入：amount = 10, coins = [10] 
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= coins.length <= 300 
// 1 <= coins[i] <= 5000 
// coins 中的所有值 互不相同 
// 0 <= amount <= 5000 
// 
//
// Related Topics 数组 动态规划 👍 1256 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-03-25 11:30:32
 * @description 518.零钱兑换 II
 */
public class CoinChangeIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new CoinChangeIi().new Solution();
		solution.change(5,new int[]{1,2,5});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*超时*/
    public int change1(int amount, int[] coins) {
		Arrays.sort(coins);
		res=0;
		dfs1(0,amount,0,coins);
		return res;
    }
	private int res;
	public void dfs1(int i,int amount,int sum,int[] coins){
		if(i>=coins.length||sum>amount){
			return;
		}
		if(sum==amount) {
			++res;
			return;
		}
		//不加当前面值，加下个
		dfs1(i+1,amount,sum,coins);
		//继续加当前面值
		dfs1(i,amount,sum+coins[i],coins);
	}
	//记忆存储的，依然超时
	public int change(int amount, int[] coins) {

		Arrays.sort(coins);
		int[][] memo = new int[coins.length][amount + 1];
		return dfs(0, amount, coins, memo);
	}

	private int dfs(int i, int amount, int[] coins, int[][] memo)  {
		if (i == coins.length) {
			return amount == 0 ? 1 : 0;
		}
		if (memo[i][amount] > 0) {
			return memo[i][amount];
		}
		int ways = 0;
		for (int count = 0; count * coins[i] <= amount; count++) {
			ways += dfs(i + 1, amount - count * coins[i], coins, memo);
		}
		memo[i][amount] = ways;
		return ways;
	}

	//dp[][]为前i件物品，凑成总和为j的方案数量
	//时间复杂度n*amount^2
	//空间复杂度 n*amount
	public int change2(int amount, int[] coins) {
		int n=coins.length;
		int [][] dp=new int[n+1][amount+1];
		dp[0][0]=1;
		for (int i = 1; i <=n; i++) {
			int v=coins[i-1];
			for (int j = 0; j <=amount; j++) {
				dp[i][j]=dp[i-1][j];
				for (int k = 1; k *v<=j ; k++) {
					dp[i][j]+=dp[i-1][j-k*v];
				}
			}
		}
		return dp[n][amount];
	}
	//一维数组优化，因为不需要保存数量
	//原始数组递增
	//转移方程修改为dp[j-v]，且遍历从当前硬币值开始
	public int change3(int amount, int[] coins) {
		int n=coins.length;
		int [] dp=new int[amount+1];
		dp[0]=1;
		for (int i = 1; i <=n; i++) {
			int v=coins[i-1];
			for (int j = v; j <=amount ; j++) {
				dp[j]+=dp[j-v];
			}
		}
		return dp[amount];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
